package ACWing.Dynamicprogramming.Backpack;
//3. 完全背包问题

/**
 * @author :chenjie
 * @date :Created 2022/11/11 17:05
 */
//超时版
//public class Completely {
//    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        int N=sc.nextInt();
//        int V= sc.nextInt();
//        int[]v=new int[N+1];//当前物体的体积
//        int[]w=new int[N+1];//当前物体的价值
//        for (int i = 0; i < N; i++) {
//            v[i+1]=sc.nextInt();
//            w[i+1]=sc.nextInt();
//        }
//        int[][]dp=new int[N+1][V+1];
//        for (int i = 1; i <N+1 ; i++) {
//            for (int j = 1; j < V+1; j++) {
//                    for (int k = 0; k <= j/v[i]; k++) {
//                        dp[i][j]=Math.max(dp[i-1][j-(v[i]*k)]+k*w[i],dp[i][j]);
//                    }
//
//
//            }
//        }
//        System.out.println(dp[N][V]);
//    }
//}


//3. 完全背包问题

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/11 17:05
 */
public class Completely {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V= sc.nextInt();
        int[]v=new int[N+1];//当前物体的体积
        int[]w=new int[N+1];//当前物体的价值
        for (int i = 0; i < N; i++) {
            v[i+1]=sc.nextInt();
            w[i+1]=sc.nextInt();
        }
        int[]dp=new int[V+1];
        for (int i = 1; i <N+1 ; i++) {
            for (int j = 1; j < V+1; j++) {

                if(j>=v[i]){
                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
                }



            }
        }
        System.out.println(dp[V]);
    }
}

